package summer.graph;

import java.util.LinkedList;
import java.util.List;

public class Solution934 {
    LinkedList<int[]> queue = new LinkedList<>();
    boolean[][] used;

    public int shortestBridge(int[][] grid) {
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        int m = grid.length;
        int n = grid[0].length;
        used = new boolean[m][n];
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfs(i, j, grid);
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        int dis = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] curs = queue.removeFirst();
                for (int i = 0; i < 4; i++) {
                    int x = curs[0] + dx[i];
                    int y = curs[1] + dy[i];
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    if (used[x][y]) continue;
                    if (grid[x][y] == 1) return dis;
                    used[x][y] = true;
                    queue.add(new int[]{x, y});
                }
            }
            dis++;
        }
        return dis;
    }

    public void dfs(int i, int j, int[][] grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
        if (used[i][j] || grid[i][j] == 0) return;
        used[i][j] = true;
        queue.add(new int[]{i, j});
        dfs(i + 1, j, grid);
        dfs(i - 1, j, grid);
        dfs(i, j + 1, grid);
        dfs(i, j - 1, grid);
    }
}
